<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>heapq 堆队列算法 | David 的博客</title><meta name="author" content="David"><meta name="copyright" content="David"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="Python heapq 堆队列算法模块解释说明源码：Lib&#x2F;heapq.py  这个模块实现了堆队列算法，即优先队列算法。 堆是一棵完全二叉树，其中每个节点的值都小于等于其各个子节点的值。这个使用数组的实现，索引从 0 开始，且对所有的 k 都有 heap[k] &lt;&#x3D; heap[2*k+1] 和 heap[k] &lt;&#x3D; heap[2*k+2]。比较时不存在的元素被认为是无限大">
<meta property="og:type" content="article">
<meta property="og:title" content="heapq 堆队列算法">
<meta property="og:url" content="https://blog.david-deng.cn/2023/10/28/heapq-%E5%A0%86%E9%98%9F%E5%88%97%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="David 的博客">
<meta property="og:description" content="Python heapq 堆队列算法模块解释说明源码：Lib&#x2F;heapq.py  这个模块实现了堆队列算法，即优先队列算法。 堆是一棵完全二叉树，其中每个节点的值都小于等于其各个子节点的值。这个使用数组的实现，索引从 0 开始，且对所有的 k 都有 heap[k] &lt;&#x3D; heap[2*k+1] 和 heap[k] &lt;&#x3D; heap[2*k+2]。比较时不存在的元素被认为是无限大">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-7.png">
<meta property="article:published_time" content="2023-10-28T05:34:19.000Z">
<meta property="article:modified_time" content="2023-11-16T13:34:32.000Z">
<meta property="article:author" content="David">
<meta property="article:tag" content="python">
<meta property="article:tag" content="heapq">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-7.png"><link rel="shortcut icon" href="/img/favicon.svg"><link rel="canonical" href="https://blog.david-deng.cn/2023/10/28/heapq-%E5%A0%86%E9%98%9F%E5%88%97%E7%AE%97%E6%B3%95/index.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload="this.media='all'"><script>
    (() => {
      
    const saveToLocal = {
      set: (key, value, ttl) => {
        if (!ttl) return
        const expiry = Date.now() + ttl * 86400000
        localStorage.setItem(key, JSON.stringify({ value, expiry }))
      },
      get: key => {
        const itemStr = localStorage.getItem(key)
        if (!itemStr) return undefined
        const { value, expiry } = JSON.parse(itemStr)
        if (Date.now() > expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return value
      }
    }

    window.btf = {
      saveToLocal,
      getScript: (url, attr = {}) => new Promise((resolve, reject) => {
        const script = document.createElement('script')
        script.src = url
        script.async = true
        Object.entries(attr).forEach(([key, val]) => script.setAttribute(key, val))
        script.onload = script.onreadystatechange = () => {
          if (!script.readyState || /loaded|complete/.test(script.readyState)) resolve()
        }
        script.onerror = reject
        document.head.appendChild(script)
      }),
      getCSS: (url, id) => new Promise((resolve, reject) => {
        const link = document.createElement('link')
        link.rel = 'stylesheet'
        link.href = url
        if (id) link.id = id
        link.onload = link.onreadystatechange = () => {
          if (!link.readyState || /loaded|complete/.test(link.readyState)) resolve()
        }
        link.onerror = reject
        document.head.appendChild(link)
      }),
      addGlobalFn: (key, fn, name = false, parent = window) => {
        if (!false && key.startsWith('pjax')) return
        const globalFn = parent.globalFn || {}
        globalFn[key] = globalFn[key] || {}
        globalFn[key][name || Object.keys(globalFn[key]).length] = fn
        parent.globalFn = globalFn
      }
    }
  
      
      const activateDarkMode = () => {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      const activateLightMode = () => {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }

      btf.activateDarkMode = activateDarkMode
      btf.activateLightMode = activateLightMode

      const theme = saveToLocal.get('theme')
    
          const mediaQueryDark = window.matchMedia('(prefers-color-scheme: dark)')
          const mediaQueryLight = window.matchMedia('(prefers-color-scheme: light)')
          
          if (theme === undefined) {
            if (mediaQueryLight.matches) activateLightMode()
            else if (mediaQueryDark.matches) activateDarkMode()
            else {
              const hour = new Date().getHours()
              const isNight = hour <= 6 || hour >= 18
              isNight ? activateDarkMode() : activateLightMode()
            }
            mediaQueryDark.addEventListener('change', () => {
              if (saveToLocal.get('theme') === undefined) {
                e.matches ? activateDarkMode() : activateLightMode()
              }
            })
          } else {
            theme === 'light' ? activateLightMode() : activateDarkMode()
          }
        
      
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        document.documentElement.classList.toggle('hide-aside', asideStatus === 'hide')
      }
    
      
    const detectApple = () => {
      if (/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)) {
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
  
    })()
  </script><script>const GLOBAL_CONFIG = {
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
  highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false,"highlightFullpage":false,"highlightMacStyle":false},
  copy: {
    success: '复制成功',
    error: '复制失败',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: false
  },
  runtime: '',
  dateSuffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: {"limitCount":50,"languages":{"author":"作者: David","link":"链接: ","source":"来源: David 的博客","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
  lightbox: 'null',
  Snackbar: {"chs_to_cht":"已切换为繁体中文","cht_to_chs":"已切换为简体中文","day_to_night":"已切换为深色模式","night_to_day":"已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#121212","position":"bottom-left"},
  infinitegrid: {
    js: 'https://cdn.jsdelivr.net/npm/@egjs/infinitegrid/dist/infinitegrid.min.js',
    buttonText: '加载更多'
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: true,
  percent: {
    toc: true,
    rightside: false,
  },
  autoDarkmode: true
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'heapq 堆队列算法',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  isShuoshuo: false
}</script><style type="text/css">#toggle-sidebar {bottom: 80px}</style><meta name="generator" content="Hexo 7.3.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img text-center"><img src="/img/avatar.png" onerror="onerror=null;src='/img/loading.gif'" alt="avatar"/></div><div class="site-data text-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">27</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">28</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">28</div></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><span class="site-page group"><i class="fa-fw fas fa-compass"></i><span> 目录</span><i class="fas fa-chevron-down"></i></span><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url(https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-7.png);"><nav id="nav"><span id="blog-info"><a class="nav-site-title" href="/"><span class="site-name">David 的博客</span></a><a class="nav-page-title" href="/"><span class="site-name">heapq 堆队列算法</span></a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><span class="site-page group"><i class="fa-fw fas fa-compass"></i><span> 目录</span><i class="fas fa-chevron-down"></i></span><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友情链接</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><span class="site-page"><i class="fas fa-bars fa-fw"></i></span></div></div></nav><div id="post-info"><h1 class="post-title">heapq 堆队列算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-10-28T05:34:19.000Z" title="发表于 2023-10-28 13:34:19">2023-10-28</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-11-16T13:34:32.000Z" title="更新于 2023-11-16 21:34:32">2023-11-16</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/python/">python</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/python/heapq/">heapq</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">总字数:</span><span class="word-count">5.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>19分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title=""><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">浏览量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="container post-content" id="article-container"><div id="post-outdate-notice" data="{&quot;limitDay&quot;:90,&quot;messagePrev&quot;:&quot;文章距离最近一次更新已经&quot;,&quot;messageNext&quot;:&quot;天，文章的内容可能已经过期。&quot;,&quot;postUpdate&quot;:&quot;2023-11-16 21:34:32&quot;}" hidden></div><h1 id="Python-heapq-堆队列算法"><a href="#Python-heapq-堆队列算法" class="headerlink" title="Python heapq 堆队列算法"></a>Python <code>heapq </code>堆队列算法</h1><h2 id="模块解释说明"><a href="#模块解释说明" class="headerlink" title="模块解释说明"></a>模块解释说明</h2><p>源码：<a target="_blank" rel="noopener external nofollow noreferrer" href="https://github.com/python/cpython/tree/3.12/Lib/heapq.py">Lib&#x2F;heapq.py</a></p>
<blockquote>
<p>这个模块实现了堆队列算法，即优先队列算法。</p>
<p>堆是一棵完全二叉树，其中每个节点的值都小于等于其各个子节点的值。这个使用数组的实现，索引从 0 开始，且对所有的 <em>k</em> 都有 <code>heap[k] &lt;= heap[2*k+1]</code> 和 <code>heap[k] &lt;= heap[2*k+2]</code>。比较时不存在的元素被认为是无限大。堆最有趣的特性在于最小的元素总是在根结点：<code>heap[0]</code>。</p>
<p>这个API与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。</p>
<p>基于这两方面，把堆看作原生的Python list也没什么奇怪的： <code>heap[0]</code> 表示最小的元素，同时 <code>heap.sort()</code> 维护了堆的不变性！</p>
<p>要创建一个堆，可以新建一个空列表 <code>[]</code>，或者用函数 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heapify"><code>heapify()</code></a> 把一个非空列表变为堆。</p>
</blockquote>
<p>总结如下：</p>
<ol>
<li><code>heapq</code> 模块实现了堆队列算法(优先队列算法)，进一步说，<code>heapq</code> 模块实现了小顶堆(小根堆)</li>
<li>介绍了堆的基本概念，堆是一个完全二叉树，满足对于所有的 <em>k</em> 都有 <code>heap[k] &lt;= heap[2*k+1]</code> 和 <code>heap[k] &lt;= heap[2*k+2]</code>。</li>
<li>由于<code>heapq</code> 模块实现的是小根堆，并且<code>heap[0]</code>表示根节点，所以可以得出结论: <code>heap[0]</code> 是最小的元素。</li>
<li>堆可以看作原生的Python list：<code>heap[0]</code> 表示最小的元素，同时 <code>heap.sort()</code> 维护了堆的不变性！要创建一个堆，可以新建一个空列表 <code>[]</code>，或者用函数 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heapify"><code>heapify()</code></a> 把一个非空列表变为堆。</li>
</ol>
<h2 id="heapq-模块中的函数"><a href="#heapq-模块中的函数" class="headerlink" title="heapq 模块中的函数"></a><code>heapq</code> 模块中的函数</h2><h3 id="heapq-heapify-x"><a href="#heapq-heapify-x" class="headerlink" title="heapq.heapify(x)"></a><code>heapq.heapify(x)</code></h3><blockquote>
<p>将list <em>x</em> 转换成堆，原地，线性时间内。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heapify</span><br><span class="line">hq = [<span class="number">1</span>, <span class="number">4</span>, <span class="number">56</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">66</span>, <span class="number">12</span>, <span class="number">98</span>, <span class="number">34</span>, <span class="number">6</span>, <span class="number">35</span>]  <span class="comment"># 创建一个 Python list</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;转换前, list hq 为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;转换后, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">转换前, list hq 为 &gt;&gt; [1, 4, 56, 2, 3, 66, 12, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">转换后, 堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-heappush-heap-item"><a href="#heapq-heappush-heap-item" class="headerlink" title="heapq.heappush(heap, item)"></a><code>heapq.heappush(heap, item)</code></h3><blockquote>
<p> 将 <em>item</em> 的值加入 <em>heap</em> 中，保持堆的不变性。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heappush, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">hq = [<span class="number">1</span>, <span class="number">4</span>, <span class="number">56</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">66</span>, <span class="number">12</span>, <span class="number">98</span>, <span class="number">34</span>, <span class="number">6</span>, <span class="number">35</span>]  <span class="comment"># 创建一个 Python list</span></span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;添加元素前, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line">heappush(hq, <span class="number">88</span>)  <span class="comment"># 将 item 的值加入 hq 中，保持堆的不变性</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;添加元素后, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">添加元素前, 堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">添加元素后, 堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35, 88]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-heappop-heap"><a href="#heapq-heappop-heap" class="headerlink" title="heapq.heappop(heap)"></a><code>heapq.heappop(heap)</code></h3><blockquote>
<p>弹出并返回 <em>heap</em> 的最小的元素，保持堆的不变性。如果堆为空，抛出 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#IndexError"><code>IndexError</code></a> 。使用 <code>heap[0]</code> ，可以只访问最小的元素而不弹出它。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heappop, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">hq = [<span class="number">1</span>, <span class="number">4</span>, <span class="number">56</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">66</span>, <span class="number">12</span>, <span class="number">98</span>, <span class="number">34</span>, <span class="number">6</span>, <span class="number">35</span>]  <span class="comment"># 创建一个 Python list</span></span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出前, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line">res = heappop(hq) <span class="comment"># 弹出并返回 hq 的最小的元素，保持堆的不变性</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出后, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">弹出前, 根节点元素为 &gt;&gt; 1</span></span><br><span class="line"><span class="string">弹出元素为 &gt;&gt; 2</span></span><br><span class="line"><span class="string">弹出后, 根节点元素为 &gt;&gt; 2</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-heappushpop-heap-item"><a href="#heapq-heappushpop-heap-item" class="headerlink" title="heapq.heappushpop(heap, item)"></a><code>heapq.heappushpop(heap, item)</code></h3><blockquote>
<p>将 <em>item</em> 放入堆中，然后弹出并返回 <em>heap</em> 的最小元素。该组合操作比先调用 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappush"><code>heappush()</code></a> 再调用 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappop"><code>heappop()</code></a> 运行起来更有效率。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heappushpop, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">hq = [<span class="number">1</span>, <span class="number">4</span>, <span class="number">56</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">66</span>, <span class="number">12</span>, <span class="number">98</span>, <span class="number">34</span>, <span class="number">6</span>, <span class="number">35</span>]  <span class="comment"># 创建一个 Python list</span></span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;插入前, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出前, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line">res = heappushpop(hq, <span class="number">88</span>) <span class="comment"># 将 item 放入堆中，然后弹出并返回 hq 的最小元素</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出元素为 &gt;&gt; <span class="subst">&#123;res&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;插入并弹出根节点后, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出后, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">插入前, 堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">弹出前, 根节点元素为 &gt;&gt; 1</span></span><br><span class="line"><span class="string">弹出元素为 &gt;&gt; 1</span></span><br><span class="line"><span class="string">插入并弹出根节点后, 堆队列为 &gt;&gt; [2, 3, 12, 4, 6, 66, 56, 98, 34, 88, 35]</span></span><br><span class="line"><span class="string">弹出后, 根节点元素为 &gt;&gt; 2</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-heapreplace-heap-item"><a href="#heapq-heapreplace-heap-item" class="headerlink" title="heapq.heapreplace(heap, item)"></a><code>heapq.heapreplace(heap, item)</code></h3><blockquote>
<p>弹出并返回 <em>heap</em> 中最小的一项，同时推入新的 <em>item</em>。 堆的大小不变。 如果堆为空则引发 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#IndexError"><code>IndexError</code></a>。</p>
<p>这个单步骤操作比 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappop"><code>heappop()</code></a> 加 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappush"><code>heappush()</code></a> 更高效，并且在使用固定大小的堆时更为适宜。 pop&#x2F;push 组合总是会从堆中返回一个元素并将其替换为 <em>item</em>。</p>
<p>返回的值可能会比新加入的值大。如果不希望如此，可改用 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappushpop"><code>heappushpop()</code></a>。它的 push&#x2F;pop 组合返回两个值中较小的一个，将较大的留在堆中。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heapreplace, heapify</span><br><span class="line"></span><br><span class="line">hq = [<span class="number">1</span>, <span class="number">4</span>, <span class="number">56</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">66</span>, <span class="number">12</span>, <span class="number">98</span>, <span class="number">34</span>, <span class="number">6</span>, <span class="number">35</span>]  <span class="comment"># 创建一个 Python list</span></span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;插入前, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出前, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line">res = heapreplace(hq, <span class="number">88</span>) <span class="comment"># 弹出并返回 hq 中最小的一项，同时推入新的 item</span></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出元素为 &gt;&gt; <span class="subst">&#123;res&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;插入并弹出根节点后, 堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;弹出后, 根节点元素为 &gt;&gt; <span class="subst">&#123;hq[<span class="number">0</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">插入前, 堆队列为 &gt;&gt; [1, 2, 12, 4, 3, 66, 56, 98, 34, 6, 35]</span></span><br><span class="line"><span class="string">弹出前, 根节点元素为 &gt;&gt; 1</span></span><br><span class="line"><span class="string">弹出元素为 &gt;&gt; 1</span></span><br><span class="line"><span class="string">插入并弹出根节点后, 堆队列为 &gt;&gt; [2, 3, 12, 4, 6, 66, 56, 98, 34, 88, 35]</span></span><br><span class="line"><span class="string">弹出后, 根节点元素为 &gt;&gt; 2</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h2 id="heapq-模块三个基于堆的通用目的函数"><a href="#heapq-模块三个基于堆的通用目的函数" class="headerlink" title="heapq 模块三个基于堆的通用目的函数"></a><code>heapq</code> 模块三个基于堆的通用目的函数</h2><h3 id="heapq-merge-iterables-key-None-reverse-False"><a href="#heapq-merge-iterables-key-None-reverse-False" class="headerlink" title="heapq.merge(iterables, key=None, reverse=False)"></a><code>heapq.merge(iterables, key=None, reverse=False)</code></h3><blockquote>
<p>将多个<code>已排序的输入</code>合并为一个<code>已排序的输出</code>（例如，合并来自多个日志文件的带时间戳的条目）。 返回已排序值的 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/glossary.html#term-iterator">iterator</a>。</p>
<p>类似于 <code>sorted(itertools.chain(*iterables))</code> 但返回一个可迭代对象，不会一次性地将数据全部放入内存，并假定每个输入流都是已排序的（从小到大）。</p>
<p>具有两个可选参数，它们都必须指定为关键字参数。</p>
<p><em>key</em> 指定带有单个参数的 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/glossary.html#term-key-function">key function</a>，用于从每个输入元素中提取比较键。 默认值为 <code>None</code> (直接比较元素)。</p>
<p><em>reverse</em> 为一个布尔值。 如果设为 <code>True</code>，则输入元素将按比较结果逆序进行合并。 要达成与 <code>sorted(itertools.chain(*iterables), reverse=True)</code> 类似的行为，所有可迭代对象必须是已从大到小排序的。</p>
<p><em>在 3.5 版更改:</em> 添加了可选的 <em>key</em> 和 <em>reverse</em> 形参。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span>  merge</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">代码功能描述：</span></span><br><span class="line"><span class="string">  1. 随机生成 4 个数组，每个数组包括 5 个数，数组中每个数的取值都在 [-100, 100] 之间</span></span><br><span class="line"><span class="string">  2. 将生成的数组按照绝对值从小到大进行排序</span></span><br><span class="line"><span class="string">  3. 使用 heapq.merge 函数合并 4 个有序的数组</span></span><br><span class="line"><span class="string">注意:</span></span><br><span class="line"><span class="string">  sorted 函数中的参数 key 和 reverse 必须和 heapq.merge 中的参数 key 和 reverse 相同</span></span><br><span class="line"><span class="string">  如果不同，则会导致排序失败，排序后的数组将是无序的数组。</span></span><br><span class="line"><span class="string">  从 heapq.merge 函数的描述中我们可以找到为啥 sorted 函数中的参数 key 和 reverse 必须和 heapq.merge 中的参数 key 和 reverse 相同</span></span><br><span class="line"><span class="string">  因为 heapq.merge 函数是将多个 **已排序的输入** 合并为一个 **已排序的输出** ，返回已排序值的 iterator。</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line">min_value, max_value, row, column = -<span class="number">100</span>, <span class="number">100</span>, <span class="number">4</span>, <span class="number">5</span></span><br><span class="line">key, reverse = <span class="keyword">lambda</span> x: x <span class="keyword">if</span> x &gt;= <span class="number">0</span> <span class="keyword">else</span> -x, <span class="literal">False</span></span><br><span class="line">data = [</span><br><span class="line">    <span class="built_in">sorted</span>(<span class="built_in">list</span>(random.sample(<span class="built_in">range</span>(min_value, max_value + <span class="number">1</span>), column)), key=key, reverse=reverse)</span><br><span class="line">    <span class="keyword">for</span> _ <span class="keyword">in</span> <span class="built_in">range</span>(row)</span><br><span class="line">]</span><br><span class="line"><span class="keyword">for</span> i, d <span class="keyword">in</span> <span class="built_in">enumerate</span>(data):</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;<span class="subst">&#123;i&#125;</span>: <span class="subst">&#123;d&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;Merged: &gt;&gt; <span class="subst">&#123;<span class="built_in">list</span>(merge(*data, key=key, reverse=reverse))&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;s</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">0: [8, -9, 37, 60, -76]</span></span><br><span class="line"><span class="string">1: [16, -18, -28, 43, 64]</span></span><br><span class="line"><span class="string">2: [-6, 19, -41, -52, 77]</span></span><br><span class="line"><span class="string">3: [32, -75, -85, -91, 91]</span></span><br><span class="line"><span class="string">Merged: &gt;&gt; [-6, 8, -9, 16, -18, 19, -28, 32, 37, -41, 43, -52, 60, 64, -75, -76, 77, -85, -91, 91]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-nlargest-n-iterable-key-None"><a href="#heapq-nlargest-n-iterable-key-None" class="headerlink" title="heapq.nlargest(n, iterable, key=None)"></a><code>heapq.nlargest(n, iterable, key=None)</code></h3><blockquote>
<p>从 <em>iterable</em> 所定义的数据集中返回前 <em>n</em> 个最大元素组成的列表。 如果提供了 <em>key</em> 则其应指定一个单参数的函数，用于从 <em>iterable</em> 的每个元素中提取比较键 (例如 <code>key=str.lower</code>)。 等价于: <code>sorted(iterable, key=key, reverse=True)[:n]</code>。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> nlargest, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">代码功能描述：</span></span><br><span class="line"><span class="string">  1. 随机生成 1 个包括 5 个数的数组，每个数的取值都在 [-100, 100] 之间</span></span><br><span class="line"><span class="string">  2. 将数组转换成堆队列</span></span><br><span class="line"><span class="string">  3. 取出堆队列中绝对值最大的 3 个值</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line">min_value, max_value, count,n = -<span class="number">100</span>, <span class="number">100</span>, <span class="number">10</span>,<span class="number">3</span></span><br><span class="line">hq = random.sample(<span class="built_in">range</span>(min_value, max_value + <span class="number">1</span>), count)  <span class="comment"># 创建一个 Python list</span></span><br><span class="line">key = <span class="keyword">lambda</span> a: a <span class="keyword">if</span> a &gt;= <span class="number">0</span> <span class="keyword">else</span> -a</span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line">largest = nlargest(n, hq, key=key)</span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;绝对值最大的 <span class="subst">&#123;n&#125;</span> 个数 &gt;&gt; <span class="subst">&#123;largest&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">堆队列为 &gt;&gt; [-86, -61, -6, -33, 8, 11, 97, 88, 82, 62]</span></span><br><span class="line"><span class="string">绝对值最大的 3 个数 &gt;&gt; [97, 88, -86]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h3 id="heapq-nsmallest-n-iterable-key-None"><a href="#heapq-nsmallest-n-iterable-key-None" class="headerlink" title="heapq.nsmallest(n, iterable, key=None)"></a><code>heapq.nsmallest(n, iterable, key=None)</code></h3><blockquote>
<p>从 <em>iterable</em> 所定义的数据集中返回前 <em>n</em> 个最小元素组成的列表。 如果提供了 <em>key</em> 则其应指定一个单参数的函数，用于从 <em>iterable</em> 的每个元素中提取比较键 (例如 <code>key=str.lower</code>)。 等价于: <code>sorted(iterable, key=key)[:n]</code>。</p>
</blockquote>
<p>示例代码：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> nsmallest, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">代码功能描述：</span></span><br><span class="line"><span class="string">  1. 随机生成 1 个包括 5 个数的数组，每个数的取值都在 [-100, 100] 之间</span></span><br><span class="line"><span class="string">  2. 将数组转换成堆队列</span></span><br><span class="line"><span class="string">  3. 取出堆队列中绝对值最小的 3 个值</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line">min_value, max_value, count,n = -<span class="number">100</span>, <span class="number">100</span>, <span class="number">10</span>,<span class="number">3</span></span><br><span class="line">hq = random.sample(<span class="built_in">range</span>(min_value, max_value + <span class="number">1</span>), count)  <span class="comment"># 创建一个 Python list</span></span><br><span class="line">key = <span class="keyword">lambda</span> a: a <span class="keyword">if</span> a &gt;= <span class="number">0</span> <span class="keyword">else</span> -a</span><br><span class="line"></span><br><span class="line">heapify(hq)  <span class="comment"># 将 hq 转换成堆队列(构建小顶堆)</span></span><br><span class="line">smallest = nsmallest(n, hq, key=key)</span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;堆队列为 &gt;&gt; <span class="subst">&#123;hq&#125;</span>&quot;</span>)</span><br><span class="line"><span class="built_in">print</span>(<span class="string">f&quot;绝对值最小的 <span class="subst">&#123;n&#125;</span> 个数 &gt;&gt; <span class="subst">&#123;smallest&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">堆队列为 &gt;&gt; [-86, -61, -6, -33, 8, 11, 97, 88, 82, 62]</span></span><br><span class="line"><span class="string">绝对值最小的 3 个数 &gt;&gt; [-6, 8, 11]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>

<h3 id="注意"><a href="#注意" class="headerlink" title="注意"></a>注意</h3><ol>
<li><code>heapq.nlargest</code>和<code>heapq.nsmallest</code>函数在 <em>n</em> 值较小时性能最好。 </li>
<li>对于更大的值，使用 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/functions.html#sorted"><code>sorted()</code></a> 函数会更有效率。</li>
<li>当 <code>n==1</code> 时，使用内置的 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/functions.html#min"><code>min()</code></a> 和 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/functions.html#max"><code>max()</code></a> 函数会更有效率。</li>
<li>如果需要重复使用这些函数，请考虑将可迭代对象转为真正的堆。</li>
</ol>
<h2 id="基本示例"><a href="#基本示例" class="headerlink" title="基本示例"></a>基本示例</h2><p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://en.wikipedia.org/wiki/Heapsort">堆排序</a> 可以通过将所有值推入堆中然后每次弹出一个最小值项来实现。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heappush, heappop, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">heap_sort</span>(<span class="params">iterable</span>):</span><br><span class="line">    hq = []</span><br><span class="line">    heapify(hq)</span><br><span class="line">    <span class="keyword">for</span> value <span class="keyword">in</span> iterable:</span><br><span class="line">        heappush(hq, value)</span><br><span class="line">    <span class="keyword">return</span> [heappop(hq) <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(hq))]</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&#x27;__main__&#x27;</span>:</span><br><span class="line">    min_value, max_value, count = -<span class="number">100</span>, <span class="number">100</span>, <span class="number">10</span></span><br><span class="line">    arr = random.sample(<span class="built_in">range</span>(min_value, max_value + <span class="number">1</span>), count)  <span class="comment"># 创建一个 Python list</span></span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;堆排序前的结果 &gt;&gt; <span class="subst">&#123;arr&#125;</span>&quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;堆排序后的结果 &gt;&gt; <span class="subst">&#123;heap_sort(arr)&#125;</span>&quot;</span>)</span><br><span class="line"> </span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">堆排序前的结果 &gt;&gt; [-87, 81, 100, 56, 10, 67, -19, -14, -7, -40]</span></span><br><span class="line"><span class="string">堆排序后的结果 &gt;&gt; [-87, -40, -19, -14, -7, 10, 56, 67, 81, 100]</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>

<p>这类似于 <code>sorted(iterable)</code>，但与 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/functions.html#sorted"><code>sorted()</code></a> 不同的是这个实现是不稳定的。</p>
<p>堆元素可以为元组。这有利于以下做法——在被跟踪的主记录旁边添一个额外的值（例如任务的优先级）用于互相比较：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> heapq <span class="keyword">import</span> heappop, heapify</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">arr = [(<span class="number">5</span>, <span class="string">&#x27;write code&#x27;</span>), (<span class="number">7</span>, <span class="string">&#x27;release product&#x27;</span>), (<span class="number">1</span>, <span class="string">&#x27;write spec&#x27;</span>), (<span class="number">3</span>, <span class="string">&#x27;create tests&#x27;</span>)] <span class="comment"># 创建一个 list</span></span><br><span class="line">heapify(arr) <span class="comment"># 将 list 转换成小顶堆</span></span><br><span class="line"><span class="built_in">print</span>(heappop(arr)) <span class="comment"># 输出小顶堆的根节点</span></span><br><span class="line"></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">运行结果:</span></span><br><span class="line"><span class="string">(1, &#x27;write spec&#x27;)</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br></pre></td></tr></table></figure>



<h2 id="优先队列实现说明"><a href="#优先队列实现说明" class="headerlink" title="优先队列实现说明"></a>优先队列实现说明</h2><p><a target="_blank" rel="noopener external nofollow noreferrer" href="https://en.wikipedia.org/wiki/Priority_queue">优先队列</a> 是堆的常用场合，并且它的实现包含了多个挑战：</p>
<ul>
<li>排序稳定性：如何让两个相同优先级的任务按它们最初被加入队列的顺序返回？</li>
<li>如果 priority 相同且 task 之间未定义默认比较顺序，则两个 (priority, task) 元组之间的比较会报错。</li>
<li>如果任务优先级发生改变，你该如何将其移至堆中的新位置？</li>
<li>或者如果一个挂起的任务需要被删除，你该如何找到它并将其移出队列？</li>
</ul>
<p>针对前两项挑战的一种解决方案是将条目保存为包含优先级、条目计数和任务对象 3 个元素的列表。 条目计数可用来打破平局，这样具有相同优先级的任务将按它们的添加顺序返回。 并且由于没有哪两个条目计数是相同的，元组比较将永远不会直接比较两个任务。</p>
<p>两个 task 之间不可比的问题的另一种解决方案是——创建一个忽略 task，只比较 priority 字段的包装器类：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> dataclasses <span class="keyword">import</span> dataclass, field</span><br><span class="line"><span class="keyword">from</span> typing <span class="keyword">import</span> <span class="type">Any</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="meta">@dataclass(<span class="params">order=<span class="literal">True</span></span>)</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">PrioritizedItem</span>:</span><br><span class="line">    priority: <span class="built_in">int</span></span><br><span class="line">    item: <span class="type">Any</span>=field(compare=<span class="literal">False</span>)</span><br></pre></td></tr></table></figure>

<p>其余的挑战主要包括找到挂起的任务并修改其优先级或将其完全移除。 找到一个任务可使用一个指向队列中条目的字典来实现。</p>
<p>移除条目或改变其优先级的操作实现起来更为困难，因为它会破坏堆结构不变量。 因此，一种可能的解决方案是将条目标记为已移除，再添加一个改变了优先级的新条目:</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">pq = []                         <span class="comment"># list of entries arranged in a heap</span></span><br><span class="line">entry_finder = &#123;&#125;               <span class="comment"># mapping of tasks to entries</span></span><br><span class="line">REMOVED = <span class="string">&#x27;&lt;removed-task&gt;&#x27;</span>      <span class="comment"># placeholder for a removed task</span></span><br><span class="line">counter = itertools.count()     <span class="comment"># unique sequence count</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">add_task</span>(<span class="params">task, priority=<span class="number">0</span></span>):</span><br><span class="line">    <span class="string">&#x27;Add a new task or update the priority of an existing task&#x27;</span></span><br><span class="line">    <span class="keyword">if</span> task <span class="keyword">in</span> entry_finder:</span><br><span class="line">        remove_task(task)</span><br><span class="line">    count = <span class="built_in">next</span>(counter)</span><br><span class="line">    entry = [priority, count, task]</span><br><span class="line">    entry_finder[task] = entry</span><br><span class="line">    heappush(pq, entry)</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">remove_task</span>(<span class="params">task</span>):</span><br><span class="line">    <span class="string">&#x27;Mark an existing task as REMOVED.  Raise KeyError if not found.&#x27;</span></span><br><span class="line">    entry = entry_finder.pop(task)</span><br><span class="line">    entry[-<span class="number">1</span>] = REMOVED</span><br><span class="line"></span><br><span class="line"><span class="keyword">def</span> <span class="title function_">pop_task</span>():</span><br><span class="line">    <span class="string">&#x27;Remove and return the lowest priority task. Raise KeyError if empty.&#x27;</span></span><br><span class="line">    <span class="keyword">while</span> pq:</span><br><span class="line">        priority, count, task = heappop(pq)</span><br><span class="line">        <span class="keyword">if</span> task <span class="keyword">is</span> <span class="keyword">not</span> REMOVED:</span><br><span class="line">            <span class="keyword">del</span> entry_finder[task]</span><br><span class="line">            <span class="keyword">return</span> task</span><br><span class="line">    <span class="keyword">raise</span> KeyError(<span class="string">&#x27;pop from an empty priority queue&#x27;</span>)</span><br></pre></td></tr></table></figure>



<h2 id="理论"><a href="#理论" class="headerlink" title="理论"></a>理论</h2><p>堆是通过数组来实现的，其中的元素从 0 开始计数，对于所有的 <em>k</em> 都有 <code>a[k] &lt;= a[2*k+1]</code> 且 <code>a[k] &lt;= a[2*k+2]</code>。 为了便于比较，不存在的元素被视为无穷大。 堆最有趣的特性在于 <code>a[0]</code> 总是其中最小的元素。</p>
<p>上面的特殊不变量是用来作为一场锦标赛的高效内存表示。 下面的数字是 <em>k</em> 而不是 <code>a[k]</code>:</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">                               <span class="number">0</span></span><br><span class="line"></span><br><span class="line">              <span class="number">1</span>                                 <span class="number">2</span></span><br><span class="line"></span><br><span class="line">      <span class="number">3</span>               <span class="number">4</span>                <span class="number">5</span>               <span class="number">6</span></span><br><span class="line"></span><br><span class="line">  <span class="number">7</span>       <span class="number">8</span>       <span class="number">9</span>       <span class="number">10</span>      <span class="number">11</span>      <span class="number">12</span>      <span class="number">13</span>      <span class="number">14</span></span><br><span class="line"></span><br><span class="line"><span class="number">15</span> <span class="number">16</span>   <span class="number">17</span> <span class="number">18</span>   <span class="number">19</span> <span class="number">20</span>   <span class="number">21</span> <span class="number">22</span>   <span class="number">23</span> <span class="number">24</span>   <span class="number">25</span> <span class="number">26</span>   <span class="number">27</span> <span class="number">28</span>   <span class="number">29</span> <span class="number">30</span></span><br></pre></td></tr></table></figure>

<p>在上面的树中，每个 <em>k</em> 单元都位于 <code>2*k+1</code> 和 <code>2*k+2</code> 之上。 体育运动中我们经常见到二元锦标赛模式，每个胜者单元都位于另两个单元之上，并且我们可以沿着树形图向下追溯胜者所遇到的所有对手。 但是，在许多采用这种锦标赛模式的计算机应用程序中，我们并不需要追溯胜者的历史。 为了获得更高的内存利用效率，当一个胜者晋级时，我们会用较低层级的另一条目来替代它，因此规则变为一个单元和它之下的两个单元包含三个不同条目，上方单元“胜过”了两个下方单元。</p>
<p>如果此堆的不变性质始终受到保护，则序号 0 显然是总的赢家。 删除它并找出“下一个”赢家的最简单算法方式是将某个输家（让我们假定是上图中的 30 号单元）移至 0 号位置，然后将这个新的 0 号沿树下行，不断进行值的交换，直到不变性质得到重建。 这显然会是树中条目总数的对数。 通过迭代所有条目，你将得到一个 O(n log n) 复杂度的排序。</p>
<p>此排序有一个很好的特性就是你可以在排序进行期间高效地插入新条目，前提是插入的条目不比你最近取出的 0 号元素“更好”。 这在模拟上下文时特别有用，在这种情况下树保存的是所有传入事件，“胜出”条件是最小调度时间。 当一个事件将其他事件排入执行计划时，它们的调试时间向未来方向延长，这样它们可方便地入堆。 因此，堆结构很适宜用来实现调度器，我的 MIDI 音序器就是用的这个 :-)。</p>
<p>用于实现调度器的各种结构都得到了充分的研究，堆是非常适宜的一种，因为它们的速度相当快，并且几乎是恒定的，最坏的情况与平均情况没有太大差别。 虽然还存在其他总体而言更高效的实现方式，但其最坏的情况却可能非常糟糕。</p>
<p>堆在大磁盘排序中也非常有用。 你应该已经了解大规模排序会有多个“运行轮次”（即预排序的序列，其大小通常与 CPU 内存容量相关），随后这些轮次会进入合并通道，轮次合并的组织往往非常巧妙 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html#id2">1</a>。 非常重要的一点是初始排序应产生尽可能长的运行轮次。 锦标赛模式是达成此目标的好办法。 如果你使用全部有用内存来进行锦标赛，替换和安排恰好适合当前运行轮次的条目，你将可以对于随机输入生成两倍于内存大小的运行轮次，对于模糊排序的输入还会有更好的效果。</p>
<p>另外，如果你输出磁盘上的第 0 个条目并获得一个可能不适合当前锦标赛的输入（因为其值要“胜过”上一个输出值），它无法被放入堆中，因此堆的尺寸将缩小。 被释放的内存可以被巧妙地立即重用以逐步构建第二个堆，其增长速度与第一个堆的缩减速度正好相同。 当第一个堆完全消失时，你可以切换新堆并启动新的运行轮次。 这样做既聪明又高效！</p>
<p>总之，堆是值得了解的有用内存结构。 我在一些应用中用到了它们，并且认为保留一个 &#39;heap&#39; 模块是很有意义的。 :-)</p>
<h2 id="异常解释"><a href="#异常解释" class="headerlink" title="异常解释"></a>异常解释</h2><h3 id="exception-IndexError"><a href="#exception-IndexError" class="headerlink" title="exception IndexError"></a><code>exception IndexError</code></h3><blockquote>
<p>当序列抽取超出范围时将被引发。 （切片索引会被静默截短到允许的范围；如果指定索引不是整数则 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#TypeError"><code>TypeError</code></a> 会被引发。）</p>
</blockquote>
<h3 id="exception-TypeError"><a href="#exception-TypeError" class="headerlink" title="exception TypeError"></a><code>exception TypeError</code></h3><blockquote>
<p>当一个操作或函数被应用于类型不适当的对象时将被引发。 关联的值是一个字符串，给出有关类型不匹配的详情。</p>
<p>此异常可以由用户代码引发，以表明尝试对某个对象进行的操作不受支持也不应当受支持。 如果某个对象应当支持给定的操作但尚未提供相应的实现，所要引发的适当异常应为 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#NotImplementedError"><code>NotImplementedError</code></a>。</p>
<p>传入参数的类型错误 (例如在要求 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/functions.html#int"><code>int</code></a> 时却传入了 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/stdtypes.html#list"><code>list</code></a>) 应当导致 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#TypeError"><code>TypeError</code></a>，但传入参数的值错误 (例如传入要求范围之外的数值) 则应当导致 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#ValueError"><code>ValueError</code></a>。</p>
</blockquote>
<h3 id="exception-ValueError"><a href="#exception-ValueError" class="headerlink" title="exception ValueError"></a><code>exception ValueError</code></h3><blockquote>
<p>当操作或函数接收到具有正确类型但值不适合的参数，并且情况不能用更精确的异常例如 <a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/exceptions.html#IndexError"><code>IndexError</code></a> 来描述时将被引发。</p>
</blockquote>
<hr>
<p>参考文章：<a target="_blank" rel="noopener external nofollow noreferrer" href="https://docs.python.org/zh-cn/3/library/heapq.html">heapq --- 堆队列算法 — Python 3.12.0 文档</a></p>
<p>如有侵权行为，请告知删除。</p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta"><i class="fas fa-circle-user fa-fw"></i>文章作者: </span><span class="post-copyright-info"><a href="https://blog.david-deng.cn">David</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta"><i class="fas fa-square-arrow-up-right fa-fw"></i>文章链接: </span><span class="post-copyright-info"><a href="https://blog.david-deng.cn/2023/10/28/heapq-%E5%A0%86%E9%98%9F%E5%88%97%E7%AE%97%E6%B3%95/">https://blog.david-deng.cn/2023/10/28/heapq-堆队列算法/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta"><i class="fas fa-circle-exclamation fa-fw"></i>版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow noreferrer" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来源 <a href="https://blog.david-deng.cn" target="_blank">David 的博客</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/python/">python</a><a class="post-meta__tags" href="/tags/heapq/">heapq</a></div><div class="post-share"><div class="social-share" data-image="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-7.png" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i>赞助</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="https://cdn.jsdelivr.net/gh/David-deng-01/images/blog/WeChatPay.jpg" rel="external nofollow noreferrer" target="_blank"><img class="post-qr-code-img" src="https://cdn.jsdelivr.net/gh/David-deng-01/images/blog/WeChatPay.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="https://cdn.jsdelivr.net/gh/David-deng-01/images/blog/Alipay.jpg" rel="external nofollow noreferrer" target="_blank"><img class="post-qr-code-img" src="https://cdn.jsdelivr.net/gh/David-deng-01/images/blog/Alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><a class="pagination-related" href="/2023/10/25/1%202023-10-25%20%E7%BB%84%E4%BC%9A%E5%88%86%E4%BA%AB/" title="【2023-10-25 组会分享】大语言模型综述"><img class="cover" src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-2.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="info"><div class="info-1"><div class="info-item-1">上一篇</div><div class="info-item-2">【2023-10-25 组会分享】大语言模型综述</div></div><div class="info-2"><div class="info-item-1">大语言模型综述A Survey of Large Language Models 文章基本信息如下  文章名字：A Survey of Large Language Models 发表时间：2023年3月 发表期刊：arxiv(预印版) 发表机构：中国人民大学 - AI Box小组 (ruc.edu.cn)   0 摘要 (Abstract) 时代背景：  自从20世纪50年代图灵测试被提出以来，人类一直在探索如何用机器掌握语言智能。 近年来，通过在大规模语料库上对Transformer 模型进行预训练，人们提出了预训练语言模型（Pre-training Language Model, PLM），其在解决各种自然语言处理（Natural Language Processing, NLP）任务方面表现出强大的能力。 近年来，学术界和工业界极大地 推进了针对LLM的研究，其中一个显著的进展是推出了ChatGPT（一种基于LLM开发的强大AI聊天机器人），它引起了社会的广泛 关注。    研究发现：  研究人员发现扩展模型规模可以提高模型能力，因此他们通过将参数增加到更大的...</div></div></div></a><a class="pagination-related" href="/2023/10/30/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" title="二分查找"><img class="cover" src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-1.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="info text-right"><div class="info-1"><div class="info-item-1">下一篇</div><div class="info-item-2">二分查找</div></div><div class="info-2"><div class="info-item-1">二分查找二分查找的概念 一些网站对于二分查找的解释  百度百科：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。  菜鸟教程：二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。   wikipedia：在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search...</div></div></div></a></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><a class="pagination-related" href="/2023/12/30/%E6%A0%A1%E5%9B%AD%E7%BD%91%E8%87%AA%E5%8A%A8%E7%99%BB%E5%BD%95%E8%84%9A%E6%9C%AC/" title="校园网自动登录脚本"><img class="cover" src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-9.png" alt="cover"><div class="info text-center"><div class="info-1"><div class="info-item-1"><i class="far fa-calendar-alt fa-fw"></i> 2023-12-30</div><div class="info-item-2">校园网自动登录脚本</div></div><div class="info-2"><div class="info-item-1">校园网自动登录脚本</div></div></div></a></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info text-center"><div class="avatar-img"><img src="/img/avatar.png" onerror="this.onerror=null;this.src='/img/loading.gif'" alt="avatar"/></div><div class="author-info-name">David</div><div class="author-info-description">Welcome to David's Blog</div><div class="site-data"><a href="/archives/"><div class="headline">文章</div><div class="length-num">27</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">28</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">28</div></a></div><a id="card-info-btn" target="_blank" rel="noopener external nofollow noreferrer" href="https://github.com/david-deng-01"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons"><a class="social-icon" href="https://github.com/david-deng-01" rel="external nofollow noreferrer" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="https://blog.csdn.net/David_0925" rel="external nofollow noreferrer" target="_blank" title="CSDN"><i class="fa fa-book-open"></i></a><a class="social-icon" href="tencent://AddContact/?fromId=45&amp;fromSubId=1&amp;subcmd=all&amp;uin=635647792&amp;website=www.oicqzone.com" rel="external nofollow noreferrer" target="_blank" title="QQ"><i class="fab fa-qq"></i></a><a class="social-icon" href="mailto:david-deng-0925@qq.com" rel="external nofollow noreferrer" target="_blank" title="Email"><i class="fas fa-envelope-open-text"></i></a></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#Python-heapq-%E5%A0%86%E9%98%9F%E5%88%97%E7%AE%97%E6%B3%95"><span class="toc-number">1.</span> <span class="toc-text">Python heapq 堆队列算法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A8%A1%E5%9D%97%E8%A7%A3%E9%87%8A%E8%AF%B4%E6%98%8E"><span class="toc-number">1.1.</span> <span class="toc-text">模块解释说明</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#heapq-%E6%A8%A1%E5%9D%97%E4%B8%AD%E7%9A%84%E5%87%BD%E6%95%B0"><span class="toc-number">1.2.</span> <span class="toc-text">heapq 模块中的函数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-heapify-x"><span class="toc-number">1.2.1.</span> <span class="toc-text">heapq.heapify(x)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-heappush-heap-item"><span class="toc-number">1.2.2.</span> <span class="toc-text">heapq.heappush(heap, item)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-heappop-heap"><span class="toc-number">1.2.3.</span> <span class="toc-text">heapq.heappop(heap)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-heappushpop-heap-item"><span class="toc-number">1.2.4.</span> <span class="toc-text">heapq.heappushpop(heap, item)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-heapreplace-heap-item"><span class="toc-number">1.2.5.</span> <span class="toc-text">heapq.heapreplace(heap, item)</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#heapq-%E6%A8%A1%E5%9D%97%E4%B8%89%E4%B8%AA%E5%9F%BA%E4%BA%8E%E5%A0%86%E7%9A%84%E9%80%9A%E7%94%A8%E7%9B%AE%E7%9A%84%E5%87%BD%E6%95%B0"><span class="toc-number">1.3.</span> <span class="toc-text">heapq 模块三个基于堆的通用目的函数</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-merge-iterables-key-None-reverse-False"><span class="toc-number">1.3.1.</span> <span class="toc-text">heapq.merge(iterables, key&#x3D;None, reverse&#x3D;False)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-nlargest-n-iterable-key-None"><span class="toc-number">1.3.2.</span> <span class="toc-text">heapq.nlargest(n, iterable, key&#x3D;None)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#heapq-nsmallest-n-iterable-key-None"><span class="toc-number">1.3.3.</span> <span class="toc-text">heapq.nsmallest(n, iterable, key&#x3D;None)</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B3%A8%E6%84%8F"><span class="toc-number">1.3.4.</span> <span class="toc-text">注意</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E6%9C%AC%E7%A4%BA%E4%BE%8B"><span class="toc-number">1.4.</span> <span class="toc-text">基本示例</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E8%AF%B4%E6%98%8E"><span class="toc-number">1.5.</span> <span class="toc-text">优先队列实现说明</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%90%86%E8%AE%BA"><span class="toc-number">1.6.</span> <span class="toc-text">理论</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%82%E5%B8%B8%E8%A7%A3%E9%87%8A"><span class="toc-number">1.7.</span> <span class="toc-text">异常解释</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#exception-IndexError"><span class="toc-number">1.7.1.</span> <span class="toc-text">exception IndexError</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#exception-TypeError"><span class="toc-number">1.7.2.</span> <span class="toc-text">exception TypeError</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#exception-ValueError"><span class="toc-number">1.7.3.</span> <span class="toc-text">exception ValueError</span></a></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2025/01/05/other-%E9%9A%8F%E7%AC%94-icarus-%E4%B8%BB%E9%A2%98%E5%AE%89%E8%A3%85/" title="Hexo 配置 Icarus 主题"><img src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-4.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Hexo 配置 Icarus 主题"/></a><div class="content"><a class="title" href="/2025/01/05/other-%E9%9A%8F%E7%AC%94-icarus-%E4%B8%BB%E9%A2%98%E5%AE%89%E8%A3%85/" title="Hexo 配置 Icarus 主题">Hexo 配置 Icarus 主题</a><time datetime="2025-01-05T08:25:00.000Z" title="发表于 2025-01-05 16:25:00">2025-01-05</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2024/03/18/other-leetcode-%E3%80%902024-03-18-LeetCode-%E5%88%B7%E9%A2%98-400%E9%81%93%E6%89%93%E5%8D%A1%E3%80%91/" title="LeetCode刷题400道打卡"><img src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-9.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LeetCode刷题400道打卡"/></a><div class="content"><a class="title" href="/2024/03/18/other-leetcode-%E3%80%902024-03-18-LeetCode-%E5%88%B7%E9%A2%98-400%E9%81%93%E6%89%93%E5%8D%A1%E3%80%91/" title="LeetCode刷题400道打卡">LeetCode刷题400道打卡</a><time datetime="2024-03-17T16:00:00.000Z" title="发表于 2024-03-18 00:00:00">2024-03-18</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2024/01/04/2024-01-05%20%E5%A4%9A%E6%A8%A1%E6%80%81%E6%A8%A1%E5%9E%8B%E7%BB%BC%E8%BF%B0/" title="多模态基础模型：从专家到通用助理"><img src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-7.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="多模态基础模型：从专家到通用助理"/></a><div class="content"><a class="title" href="/2024/01/04/2024-01-05%20%E5%A4%9A%E6%A8%A1%E6%80%81%E6%A8%A1%E5%9E%8B%E7%BB%BC%E8%BF%B0/" title="多模态基础模型：从专家到通用助理">多模态基础模型：从专家到通用助理</a><time datetime="2024-01-04T14:42:08.000Z" title="发表于 2024-01-04 22:42:08">2024-01-04</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2023/12/30/%E6%A0%A1%E5%9B%AD%E7%BD%91%E8%87%AA%E5%8A%A8%E7%99%BB%E5%BD%95%E8%84%9A%E6%9C%AC/" title="校园网自动登录脚本"><img src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-9.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="校园网自动登录脚本"/></a><div class="content"><a class="title" href="/2023/12/30/%E6%A0%A1%E5%9B%AD%E7%BD%91%E8%87%AA%E5%8A%A8%E7%99%BB%E5%BD%95%E8%84%9A%E6%9C%AC/" title="校园网自动登录脚本">校园网自动登录脚本</a><time datetime="2023-12-30T09:21:30.000Z" title="发表于 2023-12-30 17:21:30">2023-12-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2023/11/24/%E5%A4%9A%E6%A8%A1%E6%80%81%E8%AE%BD%E5%88%BA%E8%AF%86%E5%88%AB%E5%9F%BA%E7%BA%BF%E6%A8%A1%E5%9E%8B%E5%A4%8D%E7%8E%B0/" title="多模态讽刺识别基线模型复现"><img src="https://jsd.012700.xyz/gh/jerryc127/CDN/img/material-10.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="多模态讽刺识别基线模型复现"/></a><div class="content"><a class="title" href="/2023/11/24/%E5%A4%9A%E6%A8%A1%E6%80%81%E8%AE%BD%E5%88%BA%E8%AF%86%E5%88%AB%E5%9F%BA%E7%BA%BF%E6%A8%A1%E5%9E%8B%E5%A4%8D%E7%8E%B0/" title="多模态讽刺识别基线模型复现">多模态讽刺识别基线模型复现</a><time datetime="2023-11-24T08:51:18.000Z" title="发表于 2023-11-24 16:51:18">2023-11-24</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2022 - 2025 By David</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener external nofollow noreferrer" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener external nofollow noreferrer" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text"><a href="http://www.beian.gov.cn/portal/registerSystemInfo" rel="external nofollow noreferrer" target="_blank"> <img style="vertical-align:middle; width:20px; " src="https://cdn.jsdelivr.net/gh/David-deng-01/images/blog/icp.png"> 赣公网安备36082302000135号</a> <a href="https://beian.miit.gov.cn/" rel="external nofollow noreferrer" id="beian"  target="_blank">赣ICP备2023013705号-1</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="日间和夜间模式切换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><div class="js-pjax"></div><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="false" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-nest.min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>